package com.cjm.algorithm.tree;

import com.cjm.algorithm.TreeNode;

import java.util.*;

public class Ti437 {
    public static void main(String[] args) {
        Ti437 ti437 = new Ti437();
        System.err.println(ti437.pathSum(TreeNode.generatorTreeNode(new Integer[]{10, 5, -3, 3, 2, null, 11, 3, -2, null, 1}), 8));
        System.err.println(ti437.pathSum(TreeNode.generatorTreeNode(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,5,1}), 22));
    }

    int num = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        num = 0;
        res.clear();
        // 这里使用前序遍历+递归
        res.put(0L,1L);
        methodPathSum437(root, targetSum, 0L);
        // 遍历到一个点时， 当前的和是多少？
        // 到达这个和的方式有多少种？
        // 到当前这个节点一个sum是多少？
        // 目标的和是多少？
        // 这里走前序遍历
        return num;
    }

    Map<Long, Long> res = new HashMap<>();
    private void methodPathSum437(TreeNode root, int targetSum, long curSum) {
        // 加上当前值后， 当前的和是多少？
        curSum+=root.val;
        num += res.getOrDefault(curSum - targetSum, 0L);
        res.put(curSum, res.getOrDefault(curSum, 0L) + 1);
        if (root.left != null) {
            methodPathSum437(root.left, targetSum, curSum);
        }
        if (root.right != null) {
            methodPathSum437(root.right, targetSum, curSum);
        }
        res.put(curSum, res.get(curSum) - 1);
    }
}
